Operating Systems Lab - Memory Simulation
In this lab, you will write a program to explore different memory allocation strategies.  Your simulation will take a file as input, and run the appropriate  memory allocation algorithm over the input file.  You will be implementing a best fit and a first fit strategy.
Getting Started:
Download the files:
memorySmall.txt:  a file containing the input for a 10 allocation run of the simulation
memoryLarge.txt: a file containing the input for a 10,000 allocation run of the simulation
freelist.h: the include file for an abstract data type representing a free list.  The free list is made up of Nodes of MemBlocks.
freelist.c: the implementation of the free list
Create a working area for your simulation.  You can do this on any machine with a working C compiler -- you do not need to do this on a lab machine.  You do not even need to do it in C, but if you use C you get the benefit of the free list data type I have provided for you.

Examine the files you downloaded:

In memorySmall.txt, each line represents one memory allocation or free  in the form of <type of allocation <id of allocation> <size of allocation>  So, given the lines below:
ALLOC 2 32
FREE 2 0
the first line says to allocate 32 bytes of memory, and keep track of it with an ID of 2.   The second line says to free the block with the ID of 2.   When a line begins with the allocation type of "FREE", you can ignore the trailing zero -- that zero is there just to make it easier to read the file.  This file will control the simulation.

You should be able to hand check your simulation results while using the memorySmall.txt file

 
Look at freelist.h to see what functions and data structures are available for you.  You have:

void insertFirst(MemBlock block);    /* insert block as the first entry in the freelist */
void insertAfter(MemBlock block, Node * location); /*insert a block in the freechain after the node location, inserts at the beginning if location is NULL */
void deleteNode(Node * oldNode);    /* delete the indicated node from the freelist */

Node * getFirst();   /* get the first node in the freelist */
Node * getLast();  /* get the last node in the freelist */

void dumpFreeList();  /* dump the free list to stdout */

There are also two structures provided in this file -- a Node and a MemBlock.  Please inspect these carefully  (read the comments!) and use appropriately.   The big idea is that you can use the functions in freelist.h/.c to do much of the work of maintaining a linked list of available memory -- the freelist.   These are just helper functions so you don't have to worry about setting next and previous pointers in a doubly linked list.  However, you will need to write code to walk the freelist at times.

Note:  you should also never need to actually invoke malloc directly for this lab.  For example, you can do something like this:

MemBlock myMemBlock;
myMemBlock.size = 32;
myMemBlock.startingAddr = 104;
insertFirst(myMemBlock);    // put myMemBlock on the beginning of the free list.

Node * last = getLast();   // get the last Node from the free list
int size = last->block.size;
int addr = last->block.startingAddr;

Of course, you can also walk the free list with a loop like this:

for (Node * ptr = getFirst(); ptr != NULL; ptr = ptr->next)
{
}

 
What you need to do:
Use the pieces provided to create a complete program that can perform first fit, best fit and worst fit allocations.  It should
•	use command line arguments to specify how the simulation should be run:
Usage: ./OS_memorySimulator <FIRST|BEST> <allocationFile> 
To help with this, you can look at the command line processing from the scheduling simulation lab.   Once you process the command line, you'll then want to initialize the simulation.
•	Initialization:
o	allocate an initial heap of size BLOCK_SIZE -- BLOCK_SIZE is defined in freelist.h.  BLOCK_SIZE is the unit of memory that the allocator will work from.  Think of it as growing the heap each time you have to allocate a new BLOCK_SIZE block of memory.
o	create a large array of MemBlocks:
MemBlock allocated[MAXSIZE];    // define MAXSIZE to be quite large -- 10,000 or so
This allocated array will hold the allocated MemBlocks during the simulation.   In this simulation, you will have the allocated array (of allocated memory) and the freelist of available memory.
·       Create an initial free list by creating a single MemBlock of BLOCKSIZE, and adding it to the free list
MemBlock initialBlock;
initialBlock.size = BLOCKSIZE;
initialBlock.startingAddress = 0;
insertFirst(initialBlock);             // this actually inserts your MemBlock onto the freelist, in the first position
You now have a free list with 256 bytes of memory

•	Now you are ready the start the simulation.
o	while (fscanf(.......) != EOF)     // try to read a line in the file, if any exist.  See the code from the simulation lab for how to use scanf. In this case, you will need to read a string, followed by two integers
•	if the line is a FREE, look in allocated[id] to find the block
•	place that block on the free list.  Unless you are a graduate student, it is not required that you maintain your free list in order (although you may choose to do so), nor that you coalesce neighboring blocks in the free list after a free occurs
•	set allocated[id].size = 0   // to indicate that the block is not currently allocated.  You could also use -1 or some other sentinel other than 0 if you prefer
•	if the line is an ALLOC, call the appropriate allocator  (Best or First, depending on what the command line said)
•	loop through the free list --- for (ptr = getFirst(); ptr != NULL; ptr = ptr->next)
•	identify the appropriate block to use (based on the type of allocation)
•	create a new MemBlock to place in the allocated[] array to indicate that the block is in use.  The startingAddress of the block should be the startingAddress of the free block you just found.  The size, of course, should be the size of the memory you are allocating.
•	place this MemBlock into the allocated array
•	for the free block you are using, calculate the new startingAddress and size once the allocation has been made, and reset the values.
•	if a memory request can not be satisfied, then the heap should be grown by 1 or more blocks of size BLOCK_SIZE  -- grow by the smallest multiple of BLOCK_SIZE that allows the request to be satisfied
•	After the entire file has been processed, report the following information:
o	how large the heap grew to (the heap should never shrink)
o	the largest free block on the free list
o	the total number of blocks on the free list
o	any remaining allocated blocks (that have not been freed).

For example, your output might look like this:

# ./OS_memorySimulator BEST ../memorySmall.txt
Running best fit simulation
Simulation complete

Heap grew to 512
Largest free block: 96, at address 321
Total free blocks: 7

Allocated blocks:
block: 3 size: 32 addr: 32
block: 8 size: 96 addr: 416
block: 9 size: 64 addr: 257
Notes:
•	You can model your command line processing and file handling on the schedulingSim.c file from the last lab.  However, the file reading is much simpler for this exercise, since you can process the file line by line immediately
•	In the small simulation, you may wish to dump out both the allocated and the free list along with each action taken.  For example,
% ./OS_memorySimulator FIRST ../memorySmall.txt
Running first fit simulation

Action: ALLOC id: 0 size: 32

Free list:
size: 224 addr: 32

Allocated blocks:
block: 0 size: 32 addr: 0
--------------------
Action: ALLOC id: 1 size: 32

Free list:
size: 192 addr: 64

Allocated blocks:
block: 0 size: 32 addr: 0
block: 1 size: 32 addr: 32
--------------------
Action: ALLOC id: 2 size: 32

Free list:
size: 160 addr: 96

Allocated blocks:
block: 0 size: 32 addr: 0
block: 1 size: 32 addr: 32
block: 2 size: 32 addr: 64
--------------------
Action: FREE id: 2 size: 0

Free list:
size: 32 addr: 64
size: 160 addr: 96

Allocated blocks:
block: 0 size: 32 addr: 0
block: 1 size: 32 addr: 32
...

Completion
Successful completion of the lab should include:
•	A working program (memorySim.c, for example) that can perform first fit and best fit allocations when requested on the command line.
•	output showing the results of your first and best allocation strategies using the file memoryLarge.txt from the moodle folder. The output must include the following information:
o	how large the heap grew to (the heap should never shrink)
o	the largest free block on the free list
o	the total number of blocks on the free list
o	the number of  allocated blocks that have not been freed at the time the simulation ends
•	A write up explaining which memory allocation scheme worked the best for the large file, and why you made that decision.  This write up should speak in terms of the trade offs of the two methods you implemented and details about why you feel your pick was "best".  It should refer to things like the number of blocks, the total amount of memory allocated, the size and location of the blocks on the free list, etc.  This should be more than a sentence, but less than a page.
IF YOU ARE BORED (for additional credit):
Implement a worst fit allocation strategy in addition to the first fit and best fit.  Add functionality so that your simulation coalesces any neighboring free blocks when freeing memory.   You should also include using any partial space in the last block of the free list when growing the memory, to reduce the amount you have to increase the heap size (although you should still allocate in BLOCK_SIZE chunks).

Your write up should include all three of your schemes.  It would also be interesting to be able to run it with and without coalescing to be able to see how much effect coalescing has, but that is not required.